package ex109;

/**
 * 储物柜问题
 */
public class CabinetProblem {
    private int capacity; // 储物柜数量和人数

    public CabinetProblem(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 使用嵌套循环模拟改变储物柜状态
     *
     * @return 结束后处于开启状态的储物柜的编号
     */
    public int[] getCabinetsOpened() {
        boolean[] cabinets = new boolean[capacity]; // 初始均为false，表示关闭
        // 外层循环每次迭代是一个人的操作
        for (int person = 0; person < cabinets.length; person++) {
            // 内层循环每次循环改变符合间隔要求的储物柜的状态
            for (int id = person; id < cabinets.length; id += person + 1) {
                cabinets[id] = !cabinets[id];
            }
        }
        int numberOfOpen = 0;
        for (boolean open : cabinets) {
            if (open) {
                numberOfOpen++;
            }
        }
        int[] result = new int[numberOfOpen];
        for (int id = 0, index = 0; id < cabinets.length; id++) {
            if (cabinets[id]) {
                result[index++] = id + 1;
            }
        }
        return result;
    }

    /**
     * 快速求解的方法
     *
     * @return
     */
    public int[] getCabinetsOpenedFast() {
        int[] result = new int[(int) Math.sqrt(capacity)];

        for (int id = 1, index = 0; id * id <= capacity; id++) {
            result[index++] = id * id;
        }

        return result;
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }
}
